SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Deterministic encryption</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Deterministic encryption</span></span>

</h1>

</header>

<p>A <b>deterministic <a href="Encryption" title="Encryption">encryption</a> scheme</b> (as opposed to a <a href="Probabilistic_encryption" title="Probabilistic encryption">probabilistic encryption</a> scheme) is a <a href="Cryptosystem" title="Cryptosystem">cryptosystem</a> which always produces the same <a href="Ciphertext" title="Ciphertext">ciphertext</a> for a given <a href="Plaintext" title="Plaintext">plaintext</a> and <a href="Encryption_key" class="mw-redirect" title="Encryption key">key</a>, even over separate executions of the encryption algorithm. Examples of deterministic encryption algorithms include <a href="RSA_(algorithm)" class="mw-redirect" title="RSA (algorithm)">RSA</a> cryptosystem (without encryption padding), and many <a href="Block_cipher" title="Block cipher">block ciphers</a> when used in <a href="Electronic_codebook" class="mw-redirect" title="Electronic codebook">ECB mode</a> or with a constant <a href="Initialization_vector" title="Initialization vector">initialization vector</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Leakage">Leakage</h2></div>

<p>Deterministic encryption can leak information to an eavesdropper, who may recognize known ciphertexts. For example, when an adversary learns that a given ciphertext corresponds to some interesting message, they can learn something every time that ciphertext is transmitted. To gain information about the meaning of various ciphertexts, an adversary might perform a statistical analysis of messages transmitted over an encrypted channel, or attempt to correlate ciphertexts with observed actions (e.g., noting that a given ciphertext is always received immediately before a submarine dive). This concern is particularly serious in the case of <a href="Public_key_cryptography" class="mw-redirect" title="Public key cryptography">public key cryptography</a>, where any party can encrypt chosen messages using a public encryption key. In this case, the adversary can build a large "dictionary" of useful plaintext/ciphertext pairs, then observe the encrypted channel for matching ciphertexts.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>While deterministic encryption schemes can never be <a href="Semantically_secure" class="mw-redirect" title="Semantically secure">semantically secure</a>, they have some advantages over probabilistic schemes.

</p>

<div class="mw-heading mw-heading3"><h3 id="Database_searching_of_encrypted_data">Database searching of encrypted data</h3></div>

<p>One primary motivation for the use of deterministic encryption is the efficient searching of encrypted data. Suppose a client wants to outsource a database to a possibly untrusted database service provider. If each entry is encrypted using a public-key cryptosystem, anyone can add to the database, and only the distinguished "receiver" who has the private key can decrypt the database entries. If, however, the receiver wants to search for a specific record in the database, this becomes very difficult. There are some Public Key encryption schemes that allow keyword search,<sup id="cite_ref-BDOP04_1-0" class="reference"><a href="#cite_note-BDOP04-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Gu06efficientpublic_2-0" class="reference"><a href="#cite_note-Gu06efficientpublic-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> however these schemes all require search time linear in the database size. If the database entries were encrypted with a deterministic scheme and sorted, then a specific field of the database could be retrieved in logarithmic time.

</p>

<div class="mw-heading mw-heading2"><h2 id="Security">Security</h2></div>

<p>Assuming that a deterministic encryption scheme is going to be used, it is important to understand what is the maximum level of security that can be guaranteed.

</p><p>A number of works have focused on this exact problem. The first work to rigorously define security for a deterministic scheme was in <a href="Crypto_(conference)" class="mw-redirect" title="Crypto (conference)">CRYPTO 2007</a>.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> This work provided fairly strong security definitions (although weaker than semantic security), and gave constructions in the <a href="Random_oracle" title="Random oracle">random oracle</a> model. Two follow-up works appeared the next year in CRYPTO 2008, giving definitional equivalences and constructions without random oracles.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Alternatives_to_deterministic_encryption">Alternatives to deterministic encryption</h2></div>

<p>To counter this problem, cryptographers proposed the notion of "randomized" or <a href="Probabilistic_encryption" title="Probabilistic encryption">probabilistic encryption</a>. Under these schemes, a given plaintext can encrypt to one of a very large set of possible ciphertexts, chosen randomly during the encryption process. Under sufficiently strong security guarantees the attacks proposed above become infeasible, as the adversary will be unable to correlate any two encryptions of the same message, or correlate a message to its ciphertext, even given access to the public encryption key. This guarantee is known as <a href="Semantic_security" title="Semantic security">semantic security</a> or <a href="Ciphertext_indistinguishability" title="Ciphertext indistinguishability">ciphertext indistinguishability</a>, and has several definitions depending on the assumed capabilities of the attacker (see <a href="Semantic_security" title="Semantic security">semantic security</a>).

</p>

<ul><li><a href="Convergent_encryption" title="Convergent encryption">Convergent encryption</a></li>

<li><a href="Format-preserving_encryption" title="Format-preserving encryption">Format-preserving encryption</a></li>

<li><a href="Searchable_symmetric_encryption" title="Searchable symmetric encryption">Searchable symmetric encryption</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBonehDi_CrescenzoOstrovskyPersiano2004" class="citation book cs1">Boneh, Dan; Di Crescenzo, Giovanni; Ostrovsky, Rafail; Persiano, Giuseppe (2004). <a rel="nofollow" class="external text" href="https://crypto.stanford.edu/~dabo/pubs/papers/encsearch.pdf">"Public Key Encryption with Keyword Search"</a> <span class="cs1-format">(PDF)</span>. <i>Advances in Cryptology - EUROCRYPT 2004</i>. Lecture Notes in Computer Science. Vol. 3027. pp. <span class="nowrap">506–</span>522. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-24676-3_30">10.1007/978-3-540-24676-3_30</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-21935-4</bdi>.</cite></span>

</li>

<li id="cite_note-Gu06efficientpublic-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Gu06efficientpublic_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFGuZhuZhang2006" class="citation book cs1">Gu, Chunxiang; Zhu, Yuefei; Zhang, Yajuan (2006). <a rel="nofollow" class="external text" href="http://eprint.iacr.org/2006/108.pdf">"Efficient Public Key Encryption with Keyword Search Schemes from Pairings"</a> <span class="cs1-format">(PDF)</span>. <i>Information Security and Cryptology</i>. Lecture Notes in Computer Science. Vol. 4990. pp. <span class="nowrap">372–</span>383. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-79499-8_29">10.1007/978-3-540-79499-8_29</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-79498-1</bdi><span class="reference-accessdate">. Retrieved <span class="nowrap">3 March</span> 2015</span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFMichel2005" class="citation book cs1">Michel, Abdalla; et al. (2005). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2005/254">"Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions"</a>. <i>Advances in Cryptology – CRYPTO 2005</i>. Lecture Notes in Computer Science. Vol. 3621. pp. <span class="nowrap">205–</span>222. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11535218_13">10.1007/11535218_13</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-28114-6</bdi>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFBellareBoldyrevaO'Neill2007" class="citation book cs1">Bellare, Mihir; Boldyreva, Alexandra; O'Neill, Adam (2007). "Deterministic and Efficiently Searchable Encryption". <i>Advances in Cryptology - CRYPTO 2007</i>. Lecture Notes in Computer Science. Vol. 4622. pp. <span class="nowrap">535–</span>552. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-74143-5_30">10.1007/978-3-540-74143-5_30</a></span>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-74142-8</bdi>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFBoldyrevaFehrO’Neill2008" class="citation book cs1">Boldyreva, Alexandra; Fehr, Serge; O’Neill, Adam (2008). "On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles". In Wagner, David (ed.). <i>Advances in Cryptology – CRYPTO 2008</i>. Lecture Notes in Computer Science. Vol. 5157. Berlin, Heidelberg: Springer. pp. <span class="nowrap">335–</span>359. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-85174-5_19">10.1007/978-3-540-85174-5_19</a></span>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-85174-5</bdi>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFBellareFischlinO’NeillRistenpart2008" class="citation book cs1">Bellare, Mihir; Fischlin, Marc; O’Neill, Adam; Ristenpart, Thomas (2008). "Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles". In Wagner, David (ed.). <i>Advances in Cryptology – CRYPTO 2008</i>. Lecture Notes in Computer Science. Vol. 5157. Berlin, Heidelberg: Springer. pp. <span class="nowrap">360–</span>378. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-85174-5_20">10.1007/978-3-540-85174-5_20</a></span>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-85174-5</bdi>.</cite></span>

</li>

</ol></div></div>

<ul><li>Mihir Bellare and Alexandra Boldyreva and Adam O'Neill, Deterministic and Efficiently Searchable Encryption, CRYPTO 2007 <a rel="nofollow" class="external autonumber" href="https://doi.org/10.1007%2F978-3-540-74143-5_30">[1]</a> <a rel="nofollow" class="external autonumber" href="http://eprint.iacr.org/2006/186">[2]</a></li>

<li>Alexandra Boldyreva and Serge Fehr and Adam O'Neill, On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles, CRYPTO 2008 <a rel="nofollow" class="external autonumber" href="https://doi.org/10.1007%2F978-3-540-85174-5_19">[3]</a> <a rel="nofollow" class="external autonumber" href="http://eprint.iacr.org/2008/352">[4]</a></li>

<li>Mihir Bellare and Marc Fischlin and Adam O'Neill and Thomas Ristenpart, Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles, CRYPTO 2008 <a rel="nofollow" class="external autonumber" href="https://doi.org/10.1007%2F978-3-540-85174-5_20">[5]</a> <a rel="nofollow" class="external autonumber" href="http://eprint.iacr.org/2008/267">[6]</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-18" href="https://en.wikipedia.org/wiki/?title=Deterministic_encryption&oldid=1296219761">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>